package 剑指II;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-19
 **/

public class Jz001整数除法 {

    /**
     * 给定两个整数 a 和 b ，求它们的除法的商 a/b ，
     * 要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
     * <p>
     * 注意：
     * 整数除法的结果应当截去（truncate）其小数部分，
     * 例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
     * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。
     * 本题中，如果除法结果溢出，则返回 231 − 1
     *  
     * 示例 1：
     * 输入：a = 15, b = 2
     * 输出：7
     * 解释：15/2 = truncate(7.5) = 7
     * 示例 2：
     * 输入：a = 7, b = -3
     * 输出：-2
     * 解释：7/-3 = truncate(-2.33333..) = -2
     * 示例 3：
     * 输入：a = 0, b = 1
     * 输出：0
     * 示例 4：
     * 输入：a = 1, b = 1
     * 输出：1
     *  
     * 提示:
     * -2^31 <= a, b <= 2^31 - 1
     * b != 0
     * 注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/
     */

    public int divide(int a, int b) {

        if (a == 0) {
            return 0;
        }

        long al = Math.abs((long) a);
        long bl = Math.abs((long) b);

        long result = this.dg(al, bl);

        if (a < 0 && b < 0) {
            if (result > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
            return (int) result;
        }

        if (a < 0 || b < 0) {
            return (int) -result;
        }

        if (result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        return (int) result;
    }

    private long dg(long a, long b) {

        if (a == b) {
            return 1;
        }

        if (a < b) {
            return 0;
        }

        long sourceB = b;
        long count = 1;

        while ((b << 1) < a) {
            b <<= 1;
            count <<= 1;
        }

        return count + this.dg(a - b, sourceB);
    }

    public static void main(String[] args) {
        Jz001整数除法 n = new Jz001整数除法();
        int result = n.divide(-1010369383, -2147483648);
        System.out.println(result);
    }

}
